package com.data.basic.chapter04;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.LinkedHashMap;

/** 链表的实现
 *      [0]→1→2→3→4→5→6→null
 *      [] 表示head指向的位置，方向为单向
 * Created by wangbing on 2018/5/2.
 */
public class LinkedListDemo01<E> {
    private Node head;
    private int size;

    public LinkedListDemo01() {
        head=null;
        size=0;
    }

    /**
     * 获取链表的元素个数
     * @param
     */
    public int  getSize(){
        return size;

    }

    /**
     * 返回链表是否为空
     * @param
     */

    public boolean isEmpty(){
        return size==0;
    }

    /**
     * 链表插入---单链表头部插入
     * @param
     */
    public void addFirst(E e){
//        Node node = new Node(e);
//        node.next = head;
//        head = node;
        head = new Node(e,head);
        size++;

    }

    /**
     *
     * @param e
     * @param index
     */
    public void add(E e,int index){
        if (index<0||index>size){
            throw new IllegalArgumentException("数组越界");
        }

        if (index==0){
            /** 因为头指针（head），没有前一个节点，所以只能特殊考虑
                但是可以引入头结点(dummyHead)来解决这一问题
         */
            addFirst(e);
        }
        Node beforeIndex = new Node(head);

//        定位到index-1的位置  ；找到待添加节点的前一个节点
        int temp = 0;
        while (temp!=index-1){
            beforeIndex = head.next;
            temp++;
        }
//        Node insertNode = new Node(e);
//        insertNode.next = beforeIndex.next;
//        beforeIndex.next = insertNode;
       beforeIndex.next = new Node(e,beforeIndex.next);

        size++;
    }

    /**
     * 在链表尾部插入一个元素
     * @param e
     */
    public void addLast(E e){
        add(e,size);
    }

    private class Node<E>{
        /**
         * 单链表的节点类
         */
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList:");
        sb.append("[");
        Node temp = new Node(head);

        for (int i=0;i<size;i++){
            sb.append(temp+",");
            temp = temp.next;


        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        LinkedListDemo01 listDemo01 = new LinkedListDemo01();
        listDemo01.addFirst(1);
        listDemo01.addFirst(1);
        listDemo01.addFirst(1);
        listDemo01.addFirst(1);
        listDemo01.add(3,3);
        System.out.println(listDemo01);
    }
}
